/**
 * @Description:
 * @Date:Create in 10:42  2022/5/12
 * 分析四种情况
 * 目标值在数组所有元素之前
 * 目标值等于数组中某一个元素
 * 目标值插入数组中的位置
 * 目标值在数组所有元素之后
 */
public class searchInsert0035 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 5, 6};
        int target = 5;
        int i = searchInsert2(nums, target);
        System.out.println(i);

    }

    //    暴力解法
    public static int searchInsert1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }

    public static int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
        return right + 1;
    }

    public static int searchInsert3(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int  mid = left + ((right - left) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                return mid;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0,0]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right)，return  right
        // 目标值在数组所有元素之后的情况 [left, right)， return right
        return right;
    }
}
